Railgun
题意
给定 ,你现在在 处跳格子,每次可以向前跳 格或者 格。
求到达 格的方案数,答案对 取模。
Nothing with me, but Forever.
给定的数据范围是一个弱化版本。
给定 n 个点权 {a},并按照规则:对于 i,j,如果 i&j=0 则对 i,j 连边,生成图 G。
现在要求 G 中的每个点都要按照如下规则加入集合 S:
求最大贡献,n≤2×103,ai≤109。
给定一棵有 n 个结点的树,每次操作选取 3 个点 i,j,k 满足 i,j 存在连边,j,k 存在连边,定义一次操作为:
求最小的操作次数使得树存在度为 n−1 的点。
现在给定一个序列 {a},令 f(i,j)=j−iai×aj。对于每个 i,计算出所有满足 j≤i×k 的 f(i,j),(其中 k 为一个小于 0.35 的常量),相对误差小于 5%。
周末的赛题,然而考场上因为 E 题的一点细节没处理好,只剩下 30 min 来写 F,想到了做法后索性就没写 Code 了。
本着来写状压的,奈何发现手算一波复杂度后感觉不对。
那么我们考虑搜索(n≤10),暴力搞的话复杂度为 O(n!×T),无法通过。
那么我们考虑使用一点点的状压思想和搜索技巧: